It is a problem in the field of computer systems to provide an inexpensive, high performance, high reliability, and high capacity disk storage device. Traditional high performance and high capacity disk devices have typically used single large expensive disks (SLED) having form factors in the range of 12 or 14 inches.
The rapid acceptance of personal computers has created a market for inexpensive small form factor drives, such as 51/4, 31/2 inch, or smaller. Consequently, a disk storage device comprising a redundant array of inexpensive disks (RAID) has become a viable alternative for storing large amounts of data.
RAID products substitute many small disk drives for a few large expensive disks to provide higher storage capacities. The drawback to replacing a single large disk with, for example, a hundred small disks, is reliability. In a disk storage device consisting of many disk drives, there is a much higher probability that one of the drives will fail making the device inoperable. However, by means of data redundancy techniques, the reliability of RAID products can be substantially improved.
RAID products typically use parity encoding to survive and recover from disk drive failures. Different levels of RAID organizations using parity encoding are currently known, see "A case for redundant arrays of inexpensive disks" David A. Patterson et al., Report No. UCB/CSD 87/891, December 1987, Computer Science Division (EECS), Berkeley, Calif. 94720. Parity data are generated by XORing data to be written with previously stored data and previously stored parity data. RAID parity protection suffers from the inherent problem that the number of I/O requests, read and writes, that must be serviced to write data are many more than would be the case with non-RAID disks.
Striping and caching are well-known techniques to improve the I/O throughput in RAID products using parity protection. Striping involves the concurrent transfer of a "stripe" of data to and from disk drives. With striping, an I/O request to transfer a stripe of data is distributed over a group of disk drives, that is, each of the disk drives transfers generally concurrently, a block of the data. For example, if there are 5 disk drives in the array, and if a stripe is defined to include 5 blocks, the entire stripe can be written to the disk drives in about 1/5th the amount of time if one block of the stripe is written to each of the disk drives concurrently.
Striping is typically used in combination with a memory buffer cache or "cache" to take advantage of the principles of locality of reference, which are well known in computer programming. These principles indicate that when data stored at one location are accessed, there is a high probability that data stored at physically adjacent locations will be accessed soon afterwards in time. By having a cache the number of physical I/O transfers are reduced since there is a high probability that the requested data are already stored in the cache.
However, in RAID products the process of writing data and parity data to the disk drives is still exceptionally tedious. In a one dimensional parity protection scheme, which is the simplest form of parity protection, one parity block is generated for each stripe. The parity block for a particular stripe is generated by XORing the data stored in a block with the data stored in the other blocks of the stripe. Typically, the parity block of a stripe is written to a different disk drive than the ones which store the data blocks of the stripe. Thus, should one of the disk drives fail, the data can be recovered, stripe by stripe, from the parity block and the blocks stored on the surviving disk drives. Similarly, any parity block stored on a failed drive can easily be regenerated from the data blocks on the surviving drives.
The process of writing a new data block generally involves the following steps: a) reading the old data block which is going to be replaced by the new data block; b) reading the old parity block for the stripe that contains the new data block; c) generating new parity data from the old data, the old parity data, and the new data; d) writing the new data block; and e) writing the new parity block.
In other words, at the time that new data are written to the disk drive, traditional RAID products typically require four I/O requests to write a single block of data, retarding actual host I/O throughput.
Therefore, it is desirable to provide a system for RAID which reduces the impact of having to process additional I/O requests to generate parity data at the time that new data is written a disk drive.